<!doctype html>



  


<html class="theme-next mist use-motion" lang="en">
<head>
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>



<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />












  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />




  
  
  
  

  
    
    
  

  

  

  

  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.0" rel="stylesheet" type="text/css" />


  <meta name="keywords" content="csapp," />








  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=5.1.0" />






<meta name="description" content="chapter 6 REVIEW">
<meta property="og:type" content="article">
<meta property="og:title" content="csapp-chapter6">
<meta property="og:url" content="https://annashuo.github.io/2017/04/08/csapp-chapter6/index.html">
<meta property="og:site_name" content="Anna's Blog">
<meta property="og:description" content="chapter 6 REVIEW">
<meta property="og:image" content="https://raw.githubusercontent.com/Annashuo/hello-world/master/memory_hierarchy.png">
<meta property="og:updated_time" content="2017-04-27T09:28:59.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="csapp-chapter6">
<meta name="twitter:description" content="chapter 6 REVIEW">
<meta name="twitter:image" content="https://raw.githubusercontent.com/Annashuo/hello-world/master/memory_hierarchy.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Mist',
    sidebar: {"position":"right","display":"post"},
    fancybox: true,
    motion: true,
    duoshuo: {
      userId: '0',
      author: 'Author'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://annashuo.github.io/2017/04/08/csapp-chapter6/"/>





  <title> csapp-chapter6 | Anna's Blog </title><!-- hexo-inject:begin --><!-- hexo-inject:end -->
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="en">

  
<!-- hexo-inject:begin --><!-- hexo-inject:end --><script>
  window.fbAsyncInit = function() {
    FB.init({
      appId      : '',
      xfbml      : true,
      version    : 'v2.6'
    });
  };

  (function(d, s, id){
     var js, fjs = d.getElementsByTagName(s)[0];
     if (d.getElementById(id)) {return;}
     js = d.createElement(s); js.id = id;
     js.src = "//connect.facebook.net/en/sdk.js";
     fjs.parentNode.insertBefore(js, fjs);
   }(document, 'script', 'facebook-jssdk'));
</script>



<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
            (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
          m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
  ga('create', 'UA-105321506-1', 'auto');
  ga('send', 'pageview');
</script>


  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?6f5ab2ef1e021070500f7228c830f3c6";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>








  
  
    
  

  <div class="container one-collumn sidebar-position-right page-post-detail ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-meta ">
  

  <div class="custom-logo-site-title">
    <a href="/"  class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <span class="site-title">Anna's Blog</span>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>
    
      <p class="site-subtitle">My heart is in the work...</p>
    
</div>

<div class="site-nav-toggle">
  <button>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
  </button>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            Home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            Categories
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            Archives
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            Tags
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
  <link itemprop="mainEntityOfPage" href="https://annashuo.github.io/2017/04/08/csapp-chapter6/">

  <span style="display:none" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <meta itemprop="name" content="Anna">
    <meta itemprop="description" content="">
    <meta itemprop="image" content="/images/avatar.gif">
  </span>

  <span style="display:none" itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
    <meta itemprop="name" content="Anna's Blog">
    <span style="display:none" itemprop="logo" itemscope itemtype="http://schema.org/ImageObject">
      <img style="display:none;" itemprop="url image" alt="Anna's Blog" src="">
    </span>
  </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
            
            
              
                csapp-chapter6
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2017-04-08T12:08:14-04:00">
                2017-04-08
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/STUDY/" itemprop="url" rel="index">
                    <span itemprop="name">STUDY</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/2017/04/08/csapp-chapter6/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count fb-comments-count" data-href="https://annashuo.github.io/2017/04/08/csapp-chapter6/" itemprop="commentCount">0</span> comments
                </a>
              </span>
            
          

          

          
          

          

          

        </div>
      </header>
    


    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>chapter 6 REVIEW</p>
<a id="more"></a>
<h3 id="DRAM-vs-SRAM"><a href="#DRAM-vs-SRAM" class="headerlink" title="DRAM vs. SRAM"></a>DRAM vs. SRAM</h3><p>SRAM is faster and significantly more expensive than DRAM. SRAM is used for cache memories, both on and off the CPU chip. DRAM is used for the main memory plus the frame buffer of a graphics system.</p>
<h3 id="Memory-Capacity-amp-Access-Time"><a href="#Memory-Capacity-amp-Access-Time" class="headerlink" title="Memory Capacity &amp; Access Time"></a>Memory Capacity &amp; Access Time</h3><span>$Capacity = \frac{\#bytes}{sector} \times \frac{average\#sectors}{track} \times \frac{\#tracks}{surface} \times \frac{\#surface}{platter} \times \frac{\#platter}{disk}$</span><!-- Has MathJax -->
<span>$access\ time=seek\ time+rotation\ latency+transfer\ time$</span><!-- Has MathJax -->
<span>$T_{ave\ rotation}(ms)=\frac{1}{2}T_{max\ rotation}=\frac{1}{RPM}\times \frac{60000ms}{1min}$</span><!-- Has MathJax -->
<span>$T_{ave\ transfer}(ms)=\frac{1}{RPM}\times \frac{1}{average\#sectors/track}\times \frac{60000ms}{1min}$</span><!-- Has MathJax -->
<h3 id="Locality"><a href="#Locality" class="headerlink" title="Locality"></a>Locality</h3><p>Programs tend to use data and insructions with address near(spatial) or equal(temporal) to those they have used recently.</p>
<h3 id="Memory-Hierarchy"><a href="#Memory-Hierarchy" class="headerlink" title="Memory Hierarchy"></a>Memory Hierarchy</h3><p><img src="https://raw.githubusercontent.com/Annashuo/hello-world/master/memory_hierarchy.png" alt="memory hierarchy"></p>
<ul>
<li>cache hit</li>
<li>cahce miss(cold misses, comflict misses, capacity misses)</li>
</ul>
<p>Each memory address has m bits that form $M=2^{m}$ unique addresses. A cache is organized as an array of $S=2^{s}$ cache sets. Each set consist of E cache lines. Each line consists of a data block of $B=2^{b}$ bytes, a valid bit that indicates whether or not the line contain meaningful information, and $t=m-(b+s)$ tag bits that uniquely identify the block stored in the cache line.</p>
<h4 id="Type-of-Cache"><a href="#Type-of-Cache" class="headerlink" title="Type of Cache:"></a>Type of Cache:</h4><ul>
<li>Direct-Mapped Cache(E=1)</li>
<li>Set Associative Cache(E!=1)</li>
<li>Fully Associative Cache(E=C/B, S=1)</li>
</ul>
<h4 id="Issue-with-Writes"><a href="#Issue-with-Writes" class="headerlink" title="Issue with Writes:"></a>Issue with Writes:</h4><ul>
<li><p>After the cache updates its copy of w, what does it do about updating the copy of w in the next lower level of the hierarchy?</p>
<ul>
<li>write-through: immediately write w’s cahce back to the next lower level.</li>
<li>write-back: writing the update block to the next lower level only when it is evicted from the cache by the replacement algrithm</li>
</ul>
</li>
<li><p>How to deal with write miss?</p>
<ul>
<li>write-allocate: loads the corresponding block from the next lower level into the cache and then updates the cache block.</li>
<li>no-write-allocate: bypasses the cache and writes the word directly to the next lower level.</li>
</ul>
</li>
</ul>
<p>write-through + no-write-allocate  vs. write-back + write-allocate</p>
<h4 id="Cache-Blocking"><a href="#Cache-Blocking" class="headerlink" title="Cache Blocking"></a>Cache Blocking</h4><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div></pre></td><td class="code"><pre><div class="line">//non-blocking,total miss: (9n/8)*n^2=9/8*n^3</div><div class="line">for(i=0;i&lt;n;i++)&#123;</div><div class="line">	for(j=0;j&lt;n;j++)&#123;</div><div class="line">		for(k=0;k&lt;n;k++)&#123;</div><div class="line">			c[i*n+j]=a[i*n+k]*b[k*n+j];</div><div class="line">		&#125;</div><div class="line">	&#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line">//blocking, total misses: nB/4*(n/B)^2=n^3/(4B)</div><div class="line">for(i=0;i&lt;n;i+=B)&#123;</div><div class="line">	for(j=0;j&lt;n;j+=B)&#123;</div><div class="line">		for(k=0;k&lt;n;k+=B)&#123;</div><div class="line">			for(i1=i;i1&lt;i+B;i1++)&#123;</div><div class="line">				for(j1=j;j1&lt;j+B;j1++)&#123;</div><div class="line">					for(k1=k;k1&lt;k+B;k1++)&#123;</div><div class="line">						c[i1*n+j1]=a[i1*n+k1]*b[k1*n+j1];</div><div class="line">					&#125;</div><div class="line">				&#125;</div><div class="line">			&#125;</div><div class="line">		&#125;</div><div class="line">	&#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>

      
    </div>

    <div>
      
        

      
    </div>

    <div>
      
        

      
    </div>


    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/csapp/" rel="tag"># csapp</a>
          
        </div>
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2017/04/08/csapp-chapter5/" rel="next" title="csapp-chapter5">
                <i class="fa fa-chevron-left"></i> csapp-chapter5
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2017/04/10/csapp-chapter7/" rel="prev" title="csapp-chapter7">
                csapp-chapter7 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </article>



    <div class="post-spread">
      
    </div>
  </div>

          
          </div>
          


          
  <div class="comments" id="comments">
    
      <div class="fb-comments"
           data-href="https://annashuo.github.io/2017/04/08/csapp-chapter6/"
           data-numposts="10"
           data-width="100%"
           data-colorscheme="light">
      </div>
    
  </div>


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            Table of Contents
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            Overview
          </li>
        </ul>
      

      <section class="site-overview sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" itemprop="image"
               src="/images/avatar.gif"
               alt="Anna" />
          <p class="site-author-name" itemprop="name">Anna</p>
          <p class="site-description motion-element" itemprop="description">My heart is in the work...</p>
        </div>
        <nav class="site-state motion-element">
        
          
            <div class="site-state-item site-state-posts">
              <a href="/archives">
                <span class="site-state-item-count">43</span>
                <span class="site-state-item-name">posts</span>
              </a>
            </div>
          

          
            <div class="site-state-item site-state-categories">
              <a href="/categories">
                <span class="site-state-item-count">6</span>
                <span class="site-state-item-name">categories</span>
              </a>
            </div>
          

          
            <div class="site-state-item site-state-tags">
              <a href="/tags">
                <span class="site-state-item-count">12</span>
                <span class="site-state-item-name">tags</span>
              </a>
            </div>
          

        </nav>

        

        <div class="links-of-author motion-element">
          
            
              <span class="links-of-author-item">
                <a href="https://github.com/Annashuo/Annashuo.github.io" target="_blank" title="GitHub">
                  
                    <i class="fa fa-fw fa-github"></i>
                  
                  GitHub
                </a>
              </span>
            
              <span class="links-of-author-item">
                <a href="http://weibo.com/u/1861044584?is_all=1" target="_blank" title="Weibo">
                  
                    <i class="fa fa-fw fa-weibo"></i>
                  
                  Weibo
                </a>
              </span>
            
          
        </div>

        
        

        
        

        


      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#DRAM-vs-SRAM"><span class="nav-number">1.</span> <span class="nav-text">DRAM vs. SRAM</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Memory-Capacity-amp-Access-Time"><span class="nav-number">2.</span> <span class="nav-text">Memory Capacity & Access Time</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Locality"><span class="nav-number">3.</span> <span class="nav-text">Locality</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Memory-Hierarchy"><span class="nav-number">4.</span> <span class="nav-text">Memory Hierarchy</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#Type-of-Cache"><span class="nav-number">4.1.</span> <span class="nav-text">Type of Cache:</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#Issue-with-Writes"><span class="nav-number">4.2.</span> <span class="nav-text">Issue with Writes:</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#Cache-Blocking"><span class="nav-number">4.3.</span> <span class="nav-text">Cache Blocking</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  
  &copy; 
  <span itemprop="copyrightYear">2018</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Anna</span>
</div>


<div class="powered-by">
  Powered by <a class="theme-link" href="https://hexo.io">Hexo</a>
</div>

<div class="theme-info">
  Theme -
  <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
    NexT.Mist
  </a>
</div>


        

        
      </div>
    </footer>

    <div class="back-to-top">
      <i class="fa fa-arrow-up"></i>
    </div>
  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  




  
  <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.0"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.0"></script>



  
  

  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.0"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.0"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.0"></script>



  



  




	





  





  

  
      <!-- UY BEGIN -->
      <script type="text/javascript" src="http://v2.uyan.cc/code/uyan.js?uid="></script>
      <!-- UY END --><!-- hexo-inject:begin --><!-- Begin: Injected MathJax -->
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({"tex2jax":{"inlineMath":[["$","$"],["\\(","\\)"]],"skipTags":["script","noscript","style","textarea","pre","code"],"processEscapes":true},"TeX":{"equationNumbers":{"autoNumber":"AMS"}}});
</script>

<script type="text/x-mathjax-config">
  MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
      all[i].SourceElement().parentNode.className += ' has-jax';
    }
  });
</script>

<script type="text/javascript" src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<!-- End: Injected MathJax -->
<!-- hexo-inject:end -->
  




  
  

  
  


  

  

  


</body>
</html>
